SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Depth-first search</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Depth-first search</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><caption class="infobox-title">Depth-first search</caption><tbody><tr><td colspan="2" class="infobox-image"><div class="infobox-caption">A tree labeled by the order in which DFS expands its nodes</div></td></tr><tr><th scope="row" class="infobox-label">Class</th><td class="infobox-data"><a href="Search_algorithm" title="Search algorithm">Search algorithm</a></td></tr><tr><th scope="row" class="infobox-label">Data structure</th><td class="infobox-data"><a href="Graph_(data_structure)" class="mw-redirect" title="Graph (data structure)">Graph</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="Time_complexity" title="Time complexity">performance</a></th><td class="infobox-data"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|+|E|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|+|E|)}</annotation>

</semantics>

</math></span><img src="./a7cf317fbe3965ae3164f28c1f6858696adb23f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.573ex; height:2.843ex;" alt="{\displaystyle O(|V|+|E|)}" loading="lazy"></span> for explicit graphs traversed without repetition, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(b^{d})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(b^{d})}</annotation>

</semantics>

</math></span><img src="./c99d691c81f015266d1626ef381d2a1a49466fbb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.672ex; height:3.176ex;" alt="{\displaystyle O(b^{d})}" loading="lazy"></span> for implicit graphs with branching factor <i>b </i> searched to depth <i>d</i></td></tr><tr><th scope="row" class="infobox-label"><a href="Best%2C_worst_and_average_case" title="Best, worst and average case">Worst-case</a> <a href="Space_complexity" title="Space complexity">space complexity</a></th><td class="infobox-data"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|)}</annotation>

</semantics>

</math></span><img src="./3486d00c2ed0f7eb1db550af8f239ad68241a6c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.664ex; height:2.843ex;" alt="{\displaystyle O(|V|)}" loading="lazy"></span> if entire graph is traversed without repetition, O(longest path length searched) = <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(bd)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(bd)}</annotation>

</semantics>

</math></span><img src="./39716f0489a8d178ee6e48d992b3b031cf987b9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.796ex; height:2.843ex;" alt="{\displaystyle O(bd)}" loading="lazy"></span>for implicit graphs without elimination of duplicate nodes</td></tr><tr><th scope="row" class="infobox-label">Optimal</th><td class="infobox-data">no (does not generally find shortest paths)</td></tr></tbody></table>

<p><b>Depth-first search</b> (<b>DFS</b>) is an <a href="Algorithm" title="Algorithm">algorithm</a> for traversing or searching <a href="Tree_data_structure" class="mw-redirect" title="Tree data structure">tree</a> or <a href="Graph_(data_structure)" class="mw-redirect" title="Graph (data structure)">graph</a> data structures. The algorithm starts at the <a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">root node</a> (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a <a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">stack</a>, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.

</p><p>A version of depth-first search was investigated in the 19th century by French mathematician <a href="Charles_Pierre_Tr%C3%A9maux" class="mw-redirect" title="Charles Pierre Trémaux">Charles Pierre Trémaux</a><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> as a strategy for <a href="Maze_solving_algorithm" class="mw-redirect" title="Maze solving algorithm">solving mazes</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Properties">Properties</h2></div>

<p>The <a href="Time_complexity" title="Time complexity">time</a> and <a href="Memory_management" title="Memory management">space</a> analysis of DFS differs according to its application area. In theoretical computer science, DFS is typically used to traverse an entire graph, and takes time <span class="nowrap"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|+|E|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|+|E|)}</annotation>

</semantics>

</math></span><img src="./a7cf317fbe3965ae3164f28c1f6858696adb23f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.573ex; height:2.843ex;" alt="{\displaystyle O(|V|+|E|)}" loading="lazy"></span>,<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></span> where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |V|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |V|}</annotation>

</semantics>

</math></span><img src="./9ddcffc28643ac01a14dd0fb32c3157859e365a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.081ex; height:2.843ex;" alt="{\displaystyle |V|}" loading="lazy"></span> is the number of <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |E|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E|}</annotation>

</semantics>

</math></span><img src="./d8c2b9637808cf805d411190b4ae017dbd4ef8d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.069ex; height:2.843ex;" alt="{\displaystyle |E|}" loading="lazy"></span> the number of <a href="Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">edges</a>. This is linear in the size of the graph. In these applications it also uses space <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|)}</annotation>

</semantics>

</math></span><img src="./3486d00c2ed0f7eb1db550af8f239ad68241a6c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.664ex; height:2.843ex;" alt="{\displaystyle O(|V|)}" loading="lazy"></span> in the worst case to store the <a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">stack</a> of vertices on the current search path as well as the set of already-visited vertices. Thus, in this setting, the time and space bounds are the same as for <a href="Breadth-first_search" title="Breadth-first search">breadth-first search</a> and the choice of which of these two algorithms to use depends less on their complexity and more on the different properties of the vertex orderings the two algorithms produce.

</p><p>For applications of DFS in relation to specific domains, such as searching for solutions in <a href="Artificial_intelligence" title="Artificial intelligence">artificial intelligence</a> or web-crawling, the graph to be traversed is often either too large to visit in its entirety or infinite (DFS may suffer from <a href="Halting_problem" title="Halting problem">non-termination</a>). In such cases, search is only performed to a <a href="Depth-limited_search" class="mw-redirect" title="Depth-limited search">limited depth</a>; due to limited resources, such as memory or disk space, one typically does not use data structures to keep track of the set of all previously visited vertices. When search is performed to a limited depth, the time is still linear in terms of the number of expanded vertices and edges (although this number is not the same as the size of the entire graph because some vertices may be searched more than once and others not at all) but the space complexity of this variant of DFS is only proportional to the depth limit, and as a result, is much smaller than the space needed for searching to the same depth using breadth-first search. For such applications, DFS also lends itself much better to <a href="Heuristics" class="mw-redirect" title="Heuristics">heuristic</a> methods for choosing a likely-looking branch. When an appropriate depth limit is not known a priori, <a href="Iterative_deepening_depth-first_search" title="Iterative deepening depth-first search">iterative deepening depth-first search</a> applies DFS repeatedly with a sequence of increasing limits. In the artificial intelligence mode of analysis, with a <a href="Branching_factor" title="Branching factor">branching factor</a> greater than one, iterative deepening increases the running time by only a constant factor over the case in which the correct depth limit is known due to the geometric growth of the number of nodes per level.

</p><p>DFS may also be used to collect a <a href="Sample_(statistics)" class="mw-redirect" title="Sample (statistics)">sample</a> of graph nodes. However, incomplete DFS, similarly to incomplete <a href="Breadth-first_search#Bias_towards_nodes_of_high_degree" title="Breadth-first search">BFS</a>, is <a href="Bias" title="Bias">biased</a> towards nodes of high <a href="Degree_(graph_theory)" title="Degree (graph theory)">degree</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>For the following graph:

</p><p><span typeof="mw:File"></span>

</p><p>A depth-first search starting at the node A, assuming that the left edges in the shown graph are chosen before right edges, and assuming the search remembers previously visited nodes and will not repeat them (since this is a small graph), will visit the nodes in the following order: A, B, D, F, E, C, G. The edges traversed in this search form a <a href="Tr%C3%A9maux_tree" title="Trémaux tree">Trémaux tree</a>, a structure with important applications in <a href="Graph_theory" title="Graph theory">graph theory</a>.

Performing the same search without remembering previously visited nodes results in visiting the nodes in the order A, B, D, F, E, A, B, D, F, E, etc. forever, caught in the A, B, D, F, E cycle and never reaching C or G.

</p><p><a href="Iterative_deepening_depth-first_search" title="Iterative deepening depth-first search">Iterative deepening</a> is one technique to avoid this infinite loop and would reach all nodes.

</p>

<div class="mw-heading mw-heading2"><h2 id="Output_of_a_depth-first_search">Output of a depth-first search</h2></div>

<p>The result of a depth-first search of a graph can be conveniently described in terms of a <a href="Spanning_tree_(mathematics)" class="mw-redirect" title="Spanning tree (mathematics)">spanning tree</a> of the vertices reached during the search. Based on this spanning tree, the edges of the original graph can be divided into three classes: <b>forward edges</b>, which point from a node of the tree to one of its descendants, <b>back edges</b>, which point from a node to one of its ancestors, and <b>cross edges</b>, which do neither. Sometimes <b>tree edges</b>, edges which belong to the spanning tree itself, are classified separately from forward edges. If the original graph is undirected then all of its edges are tree edges or back edges.

</p>

<div class="mw-heading mw-heading3"><h3 id="Vertex_orderings">Vertex orderings</h3></div>

<p>It is also possible to use depth-first search to linearly order the vertices of a graph or tree. There are four possible ways of doing this:

</p>

<ul><li>A <b>preordering</b> is a list of the vertices in the order that they were first visited by the depth-first search algorithm. This is a compact and natural way of describing the progress of the search, as was done earlier in this article. A preordering of an <a href="Parse_tree" title="Parse tree">expression tree</a> is the expression in <a href="Polish_notation" title="Polish notation">Polish notation</a>.</li>

<li>A <b>postordering</b> is a list of the vertices in the order that they were <i>last</i> visited by the algorithm. A postordering of an expression tree is the expression in <a href="Reverse_Polish_notation" title="Reverse Polish notation">reverse Polish notation</a>.</li>

<li>A <b>reverse preordering</b> is the reverse of a preordering, i.e. a list of the vertices in the opposite order of their first visit. Reverse preordering is not the same as postordering.</li>

<li>A <b>reverse postordering</b> is the reverse of a postordering, i.e. a list of the vertices in the opposite order of their last visit. Reverse postordering is not the same as preordering.</li></ul>

<p>For <a href="Binary_trees" class="mw-redirect" title="Binary trees">binary trees</a> there is additionally <b>in-ordering</b> and <b>reverse in-ordering</b>.

</p><p>For example, when searching the directed graph below beginning at node A, the sequence of traversals is either A B D B A C A or A C D C A B A (choosing to first visit B or C from A is up to the algorithm). Note that repeat visits in the form of backtracking to a node, to check if it has still unvisited neighbors, are included here (even if it is found to have none). Thus the possible preorderings are A B D C and A C D B, while the possible postorderings are D B C A and D C B A, and the possible reverse postorderings are A C B D and A B C D.

</p>

<p>Reverse postordering produces a <a href="Topological_sorting" title="Topological sorting">topological sorting</a> of any <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a>. This ordering is also useful in <a href="Control-flow_graph" title="Control-flow graph">control-flow analysis</a> as it often represents a natural linearization of the control flows. The graph above might represent the flow of control in the code fragment below, and it is natural to consider this code in the order A B C D or A C B D but not natural to use the order A B D C or A C D B.

</p>

<pre>if (<b>A</b>) then {

} else {

}

</pre>

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

</tbody></table>

</p>

<span class="calculator-field-button cdx-button cdx-button--action-default cdx-button--weight-normal cdx-button--size-medium" data-calculator-disabled="or(ifequal(node,0),ifequal(node,switch(method,1,1,2,4,3,4,4,1,5,3,6,6,7,1)))" data-calculator-for="node" data-calculator-formula="switch(method, 1,switch(node,1,0,2,1,3,5,4,2,5,4,6,3), 2,switch(node,1,5,2,4,3,6,4,0,5,2,6,1), 3,switch(node,1,3,2,5,3,6,4,0,5,4,6,2), 4,switch(node,1,0,2,6,3,1,4,5,5,2,6,3), 5,switch(node,1,6,2,5,3,0,4,2,5,1,6,3), 6,switch(node,1,2,2,4,3,6,4,5,5,3,6,0), 7,node-1)">Previous node</span> <span class="calculator-field-button cdx-button cdx-button--action-destructive cdx-button--weight-normal cdx-button--size-medium" data-calculator-disabled="ifequal(node,0)" data-calculator-for="node" data-calculator-formula="0">Restart</span> <span class="calculator-field-button cdx-button cdx-button--action-progressive cdx-button--weight-normal cdx-button--size-medium" data-calculator-disabled="ifequal(node,switch(method,1,6,2,3,3,1,4,4,5,4,6,1,7,6,7))" data-calculator-for="node" data-calculator-formula="switch(method, 1,switch(node,0,1,1,2,2,4,3,6,4,5,5,3,6,7), 2,switch(node,0,4,1,6,2,5,3,7,4,2,5,1,6,3), 3,switch(node,0,4,1,7,2,6,3,1,4,5,5,2,6,3), 4,switch(node,0,1,1,3,2,5,3,6,4,7,5,4,6,2), 5,switch(node,0,3,1,5,2,4,3,6,4,7,5,2,6,1), 6,switch(node,0,6,1,7,2,1,3,5,4,2,5,4,6,3), 7,node+1)"><span class="calculator-field" data-calculator-type="plain" data-calculator-formula="node" data-calculator-mapping="{"Next node": "default", "Start": 0}" data-calculator-aria-live="off">Start</span></span></div></div><div class="thumbcaption">Interactive depth-first search demonstration</div></div></div></div>

<p>A recursive implementation of DFS:<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<pre><b>procedure</b> DFS(<i>G</i>, <i>v</i>) <b>is</b>

label <i>v</i> as discovered

<b>for all</b> directed edges from <i>v</i> to <i>w that are</i> <b>in</b> <i>G</i>.adjacentEdges(<i>v</i>) <b>do</b>

<b>if</b> vertex <i>w</i> is not labeled as discovered <b>then</b>

recursively call DFS(<i>G</i>, <i>w</i>)

</pre>

<p>A non-recursive implementation of DFS with worst-case space complexity <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|)}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|)}</annotation>

</semantics>

</math></span><img src="./976fe7f1e011d0dcdb3d6163754c877aaad5187f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.652ex; height:2.843ex;" alt="{\displaystyle O(|E|)}" loading="lazy"></span>, with the possibility of duplicate vertices on the stack:<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<pre><b>procedure</b> DFS_iterative(<i>G</i>, <i>v</i>) <b>is</b>

let <i>S</i> be a stack

<i>S</i>.push(<i>v</i>)

<b>while</b> <i>S</i> is not empty <b>do</b>

<i>v</i> = <i>S</i>.pop()

<b>if</b> <i>v</i> is not labeled as discovered <b>then</b>

label <i>v</i> as discovered

<b>for all</b> edges from <i>v</i> to <i>w</i> <b>in</b> <i>G</i>.adjacentEdges(<i>v</i>) <b>do</b>

<i>S</i>.push(<i>w</i>)

</pre>

<p>These two variations of DFS visit the neighbors of each vertex in the opposite order from each other: the first neighbor of <i>v</i> visited by the recursive variation is the first one in the list of adjacent edges, while in the iterative variation the first visited neighbor is the last one in the list of adjacent edges. The recursive implementation will visit the nodes from the example graph in the following order: A, B, D, F, E, C, G. The non-recursive implementation will visit the nodes as: A, E, F, B, D, C, G.

</p><p>The non-recursive implementation is similar to <a href="Breadth-first_search" title="Breadth-first search">breadth-first search</a> but differs from it in two ways:

</p>

<ol><li>it uses a stack instead of a queue, and</li>

<li>it delays checking whether a vertex has been discovered until the vertex is popped from the stack rather than making this check before adding the vertex.</li></ol>

<p>If <span class="texhtml mvar" style="font-style:italic;">G</span> is a <a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">tree</a>, replacing the queue of the breadth-first search algorithm with a stack will yield a depth-first search algorithm. For general graphs, replacing the stack of the iterative depth-first search implementation with a queue would also produce a breadth-first search algorithm, although a somewhat nonstandard one.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p><p>Another possible implementation of iterative depth-first search uses a stack of <a href="Iterator" title="Iterator">iterators</a> of the list of neighbors of a node, instead of a stack of nodes. This yields the same traversal as recursive DFS.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p>

<pre><b>procedure</b> DFS_iterative(<i>G</i>, <i>v</i>) <b>is</b>

let <i>S</i> be a stack

label <i>v</i> as discovered

<i>S</i>.push(iterator of <i>G</i>.adjacentEdges(<i>v</i>))

<b>while</b> <i>S</i> is not empty <b>do</b>

<b>if</b> <i>S</i>.peek().hasNext() <b>then</b>

<i>w</i> = <i>S</i>.peek().next()

<b>if</b> <i>w</i> is not labeled as discovered <b>then</b>

label <i>w</i> as discovered

<i>S</i>.push(iterator of <i>G</i>.adjacentEdges(<i>w</i>))

<i>S</i>.pop()

</pre>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>Algorithms that use depth-first search as a building block include:

</p>

<ul><li>Finding <a href="Connected_component_(graph_theory)" class="mw-redirect" title="Connected component (graph theory)">connected components</a>.</li>

<li><a href="Topological_sorting" title="Topological sorting">Topological sorting</a>.</li>

<li>Finding 2-(edge or vertex)-connected components.</li>

<li>Finding 3-(edge or vertex)-connected components.</li>

<li>Finding the <a href="Bridge_(graph_theory)#Bridge-finding_algorithm" title="Bridge (graph theory)">bridges</a> of a graph.</li>

<li>Generating words in order to plot the <a href="Limit_set" title="Limit set">limit set</a> of a <a href="Group_(mathematics)" title="Group (mathematics)">group</a>.</li>

<li>Finding <a href="Strongly_connected_components" class="mw-redirect" title="Strongly connected components">strongly connected components</a>.</li>

<li>Determining whether a species is closer to one species or another in a phylogenetic tree.</li>

<li><a href="Planarity_testing" title="Planarity testing">Planarity testing</a>.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup></li>

<li>Solving puzzles with only one solution, such as <a href="Maze" title="Maze">mazes</a>. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)</li>

<li><a href="Maze_generation" class="mw-redirect" title="Maze generation">Maze generation</a> may use a randomized DFS.</li>

<li>Finding <a href="Biconnected_graph" title="Biconnected graph">biconnectivity in graphs</a>.</li>

<li><a href="Primogeniture#Absolute_primogeniture" title="Primogeniture">Succession</a> to the throne shared by the <a href="Commonwealth_realms" class="mw-redirect" title="Commonwealth realms">Commonwealth realms</a>.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Complexity">Complexity</h2></div>

<p>The <a href="Analysis_of_algorithms" title="Analysis of algorithms">computational complexity</a> of DFS was investigated by <a href="John_Reif" title="John Reif">John Reif</a>. More precisely, given a graph <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span>, let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O=(v_{1},\dots ,v_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O=(v_{1},\dots ,v_{n})}</annotation>

</semantics>

</math></span><img src="./90a47bca827f9a7b1d72f77316d986207d0096ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.387ex; height:2.843ex;" alt="{\displaystyle O=(v_{1},\dots ,v_{n})}" loading="lazy"></span> be the ordering computed by the standard recursive DFS algorithm. This ordering is called the lexicographic depth-first search ordering. John Reif considered the complexity of computing the lexicographic depth-first search ordering, given a graph and a source. A <a href="Decision_problem" title="Decision problem">decision version</a> of the problem (testing whether some vertex <span class="texhtml mvar" style="font-style:italic;">u</span> occurs before some vertex <span class="texhtml mvar" style="font-style:italic;">v</span> in this order) is <a href="P-complete" title="P-complete"><b>P</b>-complete</a>,<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> meaning that it is "a nightmare for <a href="Parallel_algorithm" title="Parallel algorithm">parallel processing</a>".<sup id="cite_ref-mehlhorn_13-0" class="reference"><a href="#cite_note-mehlhorn-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 189">: 189 </span></sup>

</p><p>A depth-first search ordering (not necessarily the lexicographic one), can be computed by a randomized parallel algorithm in the complexity class <a href="NC_(complexity)" title="NC (complexity)">RNC</a>.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> As of 1997, it remained unknown whether a depth-first traversal could be constructed by a deterministic parallel algorithm, in the complexity class <a href="NC_(complexity)" title="NC (complexity)">NC</a>.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Tree_traversal" title="Tree traversal">Tree traversal</a> (for details about pre-order, in-order and post-order depth-first traversal)</li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a></li>

<li><a href="Iterative_deepening_depth-first_search" title="Iterative deepening depth-first search">Iterative deepening depth-first search</a></li>

<li><a href="Search_game" title="Search game">Search game</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a href="Charles_Pierre_Tr%C3%A9maux" class="mw-redirect" title="Charles Pierre Trémaux">Charles Pierre Trémaux</a> (1859–1882) École polytechnique of Paris (X:1876), French engineer of the telegraph <br> in Public conference, December 2, 2010 – by professor Jean Pelletier-Thibert in Académie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0980-6032">0980-6032</a>)</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFEven2011" class="citation cs2"><a href="Shimon_Even" title="Shimon Even">Even, Shimon</a> (2011), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=m3QTSMYm5rkC&pg=PA46"><i>Graph Algorithms</i></a> (2nd ed.), Cambridge University Press, pp. <span class="nowrap">46–</span>48, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-73653-4</bdi></cite>.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFSedgewick2002" class="citation cs2">Sedgewick, Robert (2002), <i>Algorithms in C++: Graph Algorithms</i> (3rd ed.), Pearson Education, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-201-36118-6</bdi></cite>.</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"> Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. p.606</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">Goodrich and Tamassia; Cormen, Leiserson, Rivest, and Stein</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">Page 93, Algorithm Design, Kleinberg and Tardos</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://11011110.github.io/blog/2013/12/17/stack-based-graph-traversal.html">"Stack-based graph traversal ≠ depth first search"</a>. <i>11011110.github.io</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2020-06-10</span></span>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFSedgewick,_Robert2010" class="citation book cs1">Sedgewick, Robert (2010). <a rel="nofollow" class="external text" href="http://worldcat.org/oclc/837386973"><i>Algorithms in Java</i></a>. Addison-Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-201-36121-6</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/837386973">837386973</a>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFHopcroftTarjan1974" class="citation cs2"><a href="John_Hopcroft" title="John Hopcroft">Hopcroft, John</a>; <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (1974), <a rel="nofollow" class="external text" href="https://ecommons.cornell.edu/bitstream/1813/6011/1/73-165.pdf">"Efficient planarity testing"</a> <span class="cs1-format">(PDF)</span>, <i><a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the Association for Computing Machinery</a></i>, <b>21</b> (4): <span class="nowrap">549–</span>568, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321850.321852">10.1145/321850.321852</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1813%2F6011">1813/6011</a></span>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6279825">6279825</a></cite>.</span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFde_FraysseixOssona_de_MendezRosenstiehl2006" class="citation cs2">de Fraysseix, H.; <a href="Patrice_Ossona_de_Mendez" title="Patrice Ossona de Mendez">Ossona de Mendez, P.</a>; <a href="Pierre_Rosenstiehl" title="Pierre Rosenstiehl">Rosenstiehl, P.</a> (2006), "Trémaux Trees and Planarity", <i>International Journal of Foundations of Computer Science</i>, <b>17</b> (5): <span class="nowrap">1017–</span>1030, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0610935">math/0610935</a></span>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2006math.....10935D">2006math.....10935D</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1142%2FS0129054106004248">10.1142/S0129054106004248</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:40107560">40107560</a></cite>.</span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFBaccelliHaji-MirsadeghiKhezeli2018" class="citation cs2">Baccelli, Francois; Haji-Mirsadeghi, Mir-Omid; Khezeli, Ali (2018), "Eternal family trees and dynamics on unimodular random graphs", in Sobieczky, Florian (ed.), <i>Unimodularity in Randomly Generated Graphs: AMS Special Session, October 8–9, 2016, Denver, Colorado</i>, Contemporary Mathematics, vol. 719, Providence, Rhode Island: American Mathematical Society, pp. <span class="nowrap">85–</span>127, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1608.05940">1608.05940</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fconm%2F719%2F14471">10.1090/conm/719/14471</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4704-3914-9</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3880014">3880014</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119173820">119173820</a></cite>; see <a rel="nofollow" class="external text" href="https://books.google.com/books?id=7dV7DwAAQBAJ&pg=PA93">Example 3.7, p. 93</a></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite id="CITEREFReif1985" class="citation journal cs1">Reif, John H. (1985). "Depth-first search is inherently sequential". <i>Information Processing Letters</i>. <b>20</b> (5): <span class="nowrap">229–</span>234. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2885%2990024-9">10.1016/0020-0190(85)90024-9</a>.</cite></span>

</li>

<li id="cite_note-mehlhorn-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-mehlhorn_13-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFMehlhornSanders2008" class="citation book cs1"><a href="Kurt_Mehlhorn" title="Kurt Mehlhorn">Mehlhorn, Kurt</a>; <a href="Peter_Sanders_(computer_scientist)" title="Peter Sanders (computer scientist)">Sanders, Peter</a> (2008). <a rel="nofollow" class="external text" href="http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GraphTraversal.pdf"><i>Algorithms and Data Structures: The Basic Toolbox</i></a> <span class="cs1-format">(PDF)</span>. Springer. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150908084757/http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GraphTraversal.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2015-09-08.</cite></span>

</li>

<li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><cite id="CITEREFAggarwalAnderson1988" class="citation cs2">Aggarwal, A.; Anderson, R. J. (1988), "A random <i>NC</i> algorithm for depth first search", <i><a href="Combinatorica" title="Combinatorica">Combinatorica</a></i>, <b>8</b> (1): <span class="nowrap">1–</span>12, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02122548">10.1007/BF02122548</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0951989">0951989</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:29440871">29440871</a></cite>.</span>

</li>

<li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><cite id="CITEREFKargerMotwani1997" class="citation cs2"><a href="David_Karger" title="David Karger">Karger, David R.</a>; <a href="Rajeev_Motwani" title="Rajeev Motwani">Motwani, Rajeev</a> (1997), "An <i>NC</i> algorithm for minimum cuts", <i><a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>, <b>26</b> (1): <span class="nowrap">255–</span>272, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1701">10.1.1.33.1701</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539794273083">10.1137/S0097539794273083</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1431256">1431256</a></cite>.</span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>, and <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a>. <i><a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a></i>, Second Edition. MIT Press and McGraw-Hill, 2001. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03293-7</bdi>. Section 22.3: Depth-first search, pp. 540–549.</li>

<li><cite id="CITEREFGoodrichTamassia2001" class="citation cs2"><a href="Michael_T._Goodrich" title="Michael T. Goodrich">Goodrich, Michael T.</a>; <a href="Roberto_Tamassia" title="Roberto Tamassia">Tamassia, Roberto</a> (2001), <i>Algorithm Design: Foundations, Analysis, and Internet Examples</i>, Wiley, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-471-38365-1</bdi></cite></li>

<li><cite id="CITEREFKleinbergTardos2006" class="citation cs2"><a href="Jon_Kleinberg" title="Jon Kleinberg">Kleinberg, Jon</a>; <a href="%C3%89va_Tardos" title="Éva Tardos">Tardos, Éva</a> (2006), <i>Algorithm Design</i>, Addison Wesley, pp. <span class="nowrap">92–</span>94</cite></li>

<li><cite id="CITEREFKnuth1997" class="citation cs2"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald E.</a> (1997), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20080904163709/http://www-cs-faculty.stanford.edu/~knuth/taocp.html"><i>The Art of Computer Programming Vol 1. 3rd ed</i></a>, Boston: Addison-Wesley, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-89683-4</bdi>, <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/155842391">155842391</a>, archived from <a rel="nofollow" class="external text" href="http://www-cs-faculty.stanford.edu/~knuth/taocp.html">the original</a> on 2008-09-04<span class="reference-accessdate">, retrieved <span class="nowrap">2008-02-12</span></span></cite></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Depth-first_search" class="extiw external" title="commons:Category:Depth-first search">Depth-first search</a></span>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="http://opendatastructures.org/versions/edition-0.1e/ods-java/12_3_Graph_Traversal.html#SECTION001532000000000000000">Open Data Structures - Section 12.3.2 - Depth-First-Search</a>, <a href="Pat_Morin" title="Pat Morin">Pat Morin</a></li>

<li><a rel="nofollow" class="external text" href="http://www.boost.org/libs/graph/doc/depth_first_search.html">C++ Boost Graph Library: Depth-First Search</a></li>

<li><a rel="nofollow" class="external text" href="http://www.cs.duke.edu/csed/jawaa/DFSanim.html">Depth-First Search Animation (for a directed graph)</a></li>

<li><a rel="nofollow" class="external text" href="http://www.kirupa.com/developer/actionscript/depth_breadth_search.htm">Depth First and Breadth First Search: Explanation and Code</a></li>

<li><a rel="nofollow" class="external text" href="http://www.algolist.net/Algorithms/Graph_algorithms/Undirected/Depth-first_search">Depth-first search algorithm illustrated explanation (Java and C++ implementations)</a></li>

<li><a rel="nofollow" class="external text" href="https://code.google.com/p/yagsbpl/">YAGSBPL – A template-based C++ library for graph search and planning</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Graph_and_tree_traversal_algorithms231" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Graph_and_tree_traversal_algorithms231" style="font-size:114%;margin:0 4em"><a href="Graph_traversal" title="Graph traversal">Graph</a> and <a href="Tree_traversal" title="Tree traversal">tree</a> traversal algorithms</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_traversal" title="Graph traversal">Search</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alpha%E2%80%93beta_pruning" title="Alpha–beta pruning">α–β pruning</a></li>

<li><a href="Best-first_search" title="Best-first search">Best-first search</a></li>

<li><a href="Beam_search" title="Beam search">Beam search</a></li>

<li><a href="Bidirectional_search" title="Bidirectional search">Bidirectional search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a>

<ul><li><a href="Lexicographic_breadth-first_search" title="Lexicographic breadth-first search">Lexicographic</a></li>

<li><a href="Parallel_breadth-first_search" title="Parallel breadth-first search">Parallel</a></li></ul></li>

<li>

<ul><li><a href="Iterative_deepening_depth-first_search" title="Iterative deepening depth-first search">Iterative deepening</a></li></ul></li>

<li><a href="Fringe_search" title="Fringe search">Fringe search</a></li>

<li><a href="Jump_point_search" title="Jump point search">Jump point search</a></li>

<li><a href="Monte_Carlo_tree_search" title="Monte Carlo tree search">Monte Carlo tree search</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a></li>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li>

<li><a href="Johnson's_algorithm" title="Johnson's algorithm">Johnson's</a></li>

<li><a href="Shortest_path_faster_algorithm" class="mw-redirect" title="Shortest path faster algorithm">Shortest path faster</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka's</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal's</a></li>

<li><a href="Reverse-delete_algorithm" title="Reverse-delete algorithm">Reverse-delete</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><a href="List_of_algorithms#Graph_search" title="List of algorithms">List of graph search algorithms</a></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-23" href="https://en.wikipedia.org/wiki/?title=Depth-first_search&oldid=1302059374">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>